/*
*	递归
*/


//汉诺塔问题-递归思路
//https://leetcode.cn/problems/hanota-lcci/description/
// class Solution {
// public:
//     void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//         bfs(A,B,C,A.size());
//     }

//     //将A借助B移动N个盘子到C上
//     void bfs(vector<int>& A, vector<int>& B, vector<int>& C,int N) {
//         if(N == 1) {
//             C.push_back(A.back());
//             A.pop_back();
//             return;
//         }

//         //将A的n-1个盘子通过C移动到B (露出最大的盘子)
//         bfs(A,C,B,N-1);
//         //将最大的盘子移动到C上
//         C.push_back(A.back());
//         A.pop_back();
//         //将B中的盘子借助A移动到C上
//         bfs(B,A,C,N-1);
//     }
// };


//合并两个有序链表
//https://leetcode.cn/problems/merge-two-sorted-lists/submissions/
// class Solution {
// public:
//     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//         if(list1 == nullptr) return list2;
//         if(list2 == nullptr) return list1;

//         if(list1->val < list2->val)
//         {
//             list1->next = mergeTwoLists(list1->next,list2);
//             return list1;
//         }
//         list2->next = mergeTwoLists(list2->next,list1);
//         return list2;
//     }
// };


 //反转链表
 //https://leetcode.cn/problems/reverse-linked-list/
// class Solution {
// public:
//     ListNode* reverseList(ListNode* head) {
//         if(!head || !head->next) return head;

//         ListNode* newHead = reverseList(head->next);
//         head->next->next = head;
//         head->next = nullptr;
//         return newHead;
//     }
// };


//两两交换链表中的节点
//https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/
// class Solution {
// public:
//     ListNode* swapPairs(ListNode* head) {
//         if(!head || !head->next) return head;

//         ListNode* tmp = swapPairs(head->next->next);
//         ListNode* headnext = head->next;
//         headnext->next = head;
//         head->next = tmp;
//         return headnext;
//     }
// };


//Pow(x,n)
//https://leetcode.cn/problems/powx-n/submissions/
// class Solution {
// public:
//     double myPow(double x, int n) {
//         return n>0?_myPow(x,n):(double)1/_myPow(x,-(long long)n);
//     }

//     double _myPow(double x, long long n) {
//         if(!n) return 1;
//         double ret = myPow(x,n/2);
//         return n%2==1?ret*ret*x:ret*ret;
//     }
// };



